// 编写代码，移除未排序链表中的重复节点。保留最开始出现的节点。

// 示例1:

//  输入：[1, 2, 3, 3, 2, 1]
//  输出：[1, 2, 3]
// 示例2:

//  输入：[1, 1, 1, 1, 2]
//  输出：[1, 2]
// 提示：

// 链表长度在[0, 20000]范围内。
// 链表元素在[0, 20000]范围内。
// 进阶：

// 如果不得使用临时缓冲区，该怎么解决？


#include "stdc++.h"

// Definition for singly-linked list.
struct ListNode {
    int val;
    ListNode *next;
    ListNode(int x) : val(x), next(nullptr) {}
};

/* 哈希表 set
HashSet
时间复杂度：O(n)
空间复杂度：O(n)
*/
class Solution {
public:
    ListNode* removeDuplicateNodes(ListNode* head) {
        if (head == nullptr) {
            return nullptr;
        }
        unordered_set<int> occurred{};
        occurred.insert(head->val);
        ListNode* cur{head};
        while (cur->next) {
            ListNode* temp = cur->next;
            if (occurred.find(temp->val) == occurred.end()) {
                occurred.insert(temp->val);
                cur = cur->next;
            } else {
                temp = cur->next;
                cur->next = cur->next->next;
                delete temp; // 删除重复节点
            }
        }
        cur->next = nullptr;
        return head;
    }
};

/*  两重循环
进阶
时间复杂度：O(n^2)
空间复杂度：O(1)
*/
class Solution {
public:
    ListNode* removeDuplicateNodes(ListNode* head) {
        ListNode* cur{head};
        while (cur) {
            ListNode* temp{cur};
            while (temp->next) {
                if (temp->next->val == cur->val) {
                    ListNode* delNode{temp->next};
                    temp->next = temp->next->next;
                    delete delNode;
                } else {
                    temp = temp->next;
                }
            }
            cur = cur->next;
        }
        return head;
    }
};